package com.mrzhou.study.struct.recursion;

/**
 * 迷宫问题(回溯)
 */
public class Maze {

    public static void main(String[] args) {
        MazeMap map = new MazeMap(10, 6);
        map.initMap(); // 初始化迷宫地图
        System.out.printf("初始化的地图信息:  \n");
        map.showMap(); // 查看当前地图的情况
        map.moveTwo(1, 1); // 在输入的地图上, 小球以x=1, y=1的位置开始执行
        System.out.printf("小球走动的轨迹信息:  \n");
        map.showMap();
    }


}

class MazeMap{
    int length = 7;
    int width = 7;
    private int[][] map = new int[length][width];

    public MazeMap() { }

    public MazeMap(int length, int width) {
        this.length = length;
        this.width = width;
        map = new int[width][length];
    }

    /**
     * 小球移动的方式, 直到终点
     */
    public void move(int x, int y) { // 入参是小球的位置
        map[x][y] = 2; // 走过的路变成2
        if(map[width-2][length-2] == 2) { // 当前小球值为2时表示已到达终点位置
            return;
        }
        // 以当前小球位置开始移动, 移动的策略 下 --> 右 --> 上 --> 左
        if(isMove(x+1, y)) { // 下边
            move(x+1, y);
        } else if (isMove(x, y+1)) { // 右边
            move(x, y+1);
        } else if(isMove(x-1, y)) { // 上边
            move(x-1, y);
        } else if (isMove(x, y-1)) { // 左边
            move(x, y-1);
        } else {
            map[x][y] = 3;
        }

    }

    public void moveTwo(int x, int y) {
        map[x][y] = 2; // 走过的路变成2
        showMap();
        if(map[width-2][length-2] == 2) { // 当前小球值为2时表示已到达终点位置
            return;
        }
        // 以当前小球位置开始移动, 移动的策略 左 --> 上 --> 右 --> 下, 这种走法没办法走到终点
        if (isMove(x, y-1)) { // 左边
            moveTwo(x, y-1);
        } else if(isMove(x-1, y)) { // 上边
            moveTwo(x-1, y);
        } else if (isMove(x, y+1)) { // 右边
            moveTwo(x, y+1);
        } else if(isMove(x+1, y)) { // 下边
            moveTwo(x+1, y);
        } else {
            map[x][y] = 3;
        }
    }

    /**
     * 判断当前位置是否可以移动
     */
    public boolean isMove(int x, int y) {
        return map[x][y] == 0;
    }

    public void initMap() {
        // 设置墙, 当数组中的值为1时表示墙
        for(int i = 0; i < map.length; i++) {
            for(int y = 0; y < map[i].length; y++) {
                if(i == 0 || i == map.length -1) {
                    map[i][y] = 1;
                } else if (i == map.length / 2) {
                    for(int j = 0; j < map[i].length / 2; j++) {
                        map[i][j] = 1;
                    }
                    if(y == map[i].length -1 ) {
                        map[i][y] = 1;
                    }
                } else {
                    map[i][0] = 1;
                    map[i][map[i].length -1] = 1;
                }
            }
        }
    }



    public void showMap() {
        for(int i = 0; i < map.length; i++) {
            for(int y = 0; y < map[i].length; y++) {
                if(y == map[i].length - 1) {
                    System.out.print(map[i][y] + "\n");
                } else {
                    System.out.print(map[i][y] + "  ");
                }
            }
        }
    }

}
